The present invention is related to the creation of structures used for computer network routing tables and, in particular, for PNNI routing tables used for point-to-multipoint connections in ATM networks.
Asynchronous Transfer Mode (ATM) is a connection-oriented system. As such, connection requests need to be routed from a requesting node though the ATM network to a destination node. The ATM Forum has defined a private network-to-network or node-to-node interface (PNNM) protocol that allows easier interconnection of ATM switches. The PNNI protocol consists of two components. The first is a signaling protocol used to relay ATM connection requests within a network between a source and a destination. The second is a routing protocol used to determine the path for routing signaling requests though the ATM network. The goal of the PNNI protocol is to advertise enough information between the nodes of a network so as to allow the nodes to route call requests within the network. Ideally, every ATM switch in a network would not only know the address of every ATM attached installation but also the current available composite (VPI/VCI) for new switched virtual circuits (SVCs) to every switch. However, as ATM networks grow to include hundreds or even thousands of switches supporting tens of thousands of users and devices, such an implementation becomes unfeasible.
Nevertheless, finding the shortest or best available path from one point to another across an ATM network does require that each node know something about what the network looks like. For example, each node must know its own whereabouts in the network and be able to locate other nodes or ATM installations so that it can establish virtual circuits offering the appropriate speed and quality of service (QoS) parameters. The solution devised by the ATM Forum is a scheme that distributes and summarizes network topologies so that nodes have detailed information about their local topology and summarized information about more distant regions of the network. The PNNI protocol manages this information through the use of a hierarchical topology, along with an addressing scheme similar to that used in telephony networks.
For each node (e.g., switch) of an ATM network, a PNNI interface associates a connection between two nodes and the connection may be a physical link or a virtual path connection (VPC). In general, every PNNI-capable node has several such interfaces and each is associated with a set of parameters (usually stored in a data structure in memory), including a traffic metrics table that stores the available traffic resource parameters on the link associated with the interface (in the forward direction). These traffic metrics tables are generally two-dimensional and associate service classes with the type of traffic metrics or attributes supported by the connection. In one sense, PNNI is a link state algorithm and QoS-based routing protocol which can collect and advertise these link state parameters (i.e., the attributes and metrics that are associated with each link and node) which become the bases for routing path selections within the network.
Using PNNI, network nodes are provided with xe2x80x9creachability informationxe2x80x9d (i.e., based on the traffic metrics and attributes) about other nodes. This reachability information is used by a source node to construct a designated transit list (DTL) that describes a complete route to a destination node. The DTL is inserted into a signaling request, which is then transmitted along the path described by the DTL. Thus, using PNNI, a single connection will be set up between the source node and the destination node.
ATM nodes configured to use the PNNI routing protocol advertise the reachability of a particular ATM address over multiple ATM physical links. The various levels of the switching hierarchy established by PNNI, map different segments of the overall ATM network in different degrees of detail. By breaking a large network of ATM switches into smaller domains called peer groups, PNNI allows individual switches to navigate paths through the entire network without requiring them to store an entire map of the network in memory. PNNI organizes nodes into peer groups and nodes within a peer group elect a leader node called a peer group leader. The peer group leader summarizes information about the peer group and presents that information to the next higher level hierarchy and also instantiates a logical group node (LGN) at the next higher level. The LGN represents its own child peer group at the lower level and becomes the peer of other LGNs at its level.
Using PNNI then, nodes in an ATM network automatically form a hierarchy of peer groups according to addresses assigned by a network manager. The nodes"" ATM addresses provide the key to the structure of this hierarchy. Each peer group has its own identifier (called a peer group ID), similar to a telephone exchange or area code. For a lower level peer group this ID is similar to an area code and exchange. For a higher peer group, it would be similar to just the area code. Finally, each node within a peer group has a unique address; similar to the way each line in a telephone exchange has a unique number.
Once the PNNI hierarchy is created, peer group leaders are allocated, and routing information is exchanged. Thereafter, the ATM nodes can begin to establish SVCs between various end-stations on the network. Using the PNNI protocol, installations on remote networks can easily establish SVCs across the hierarchy with other end stations and different peer groups.
When a signaling request is received across a user-to-network interface (UNI) by an ingress node, the node will use a shortest path algorithm, such as a Dijkstra calculation, to determine a path to connect the call to the desired destination. This calculation will create a set of DTLs, and each node will have: a full, detailed path within the source node""s own peer group; a less detailed path within the parent peer groups; and even less detail on higher level peer groups, terminating in the lowest level peer group which is an ancestor of both the source and the destination nodes. Hence, using PNNI, SVCs can be set up across a network. Once the connection is established, ATM cells are forwarded by simple table lookups, e.g., using connection tables.
As indicated above, the PNNI specification requires that QoS sensitive source routing algorithms be used in the PNNI hierarchical routing environment. QoS sensitive routing implies that the route selection algorithm must determine whether a source route can support all of the QoS requirements of a request. This requires that the routing algorithm consider both link constraints and path constraints. Link constraints such as available bandwidth (AvCR) are relatively easy to deal with because links that do not meet a caller""s requirements may simply be dropped or pruned from the topology during the shortest path calculation. However, path constraints such as cell transfer delay (CTD) and cell delay variation (CDV) are more difficult to deal with because they are not dependent on a single link only and, to date, no known routing algorithm is capable of optimizing for multiple path constraints.
Of the known routing algorithms (or shortest path algorithms), on demand routing has gained some popularity. Indeed, one method of on-demand routing is presented as an appendix to the ATM Forum""s PNNI specification. In general, on-demand routing performs a separate route computation for each requested route. On-demand routing according to this method optimizes on a single path constraint while pruning links that do not meet the caller""s requirements.
Another routing scheme proposed in the PNNI specification uses pre-computed routes. In this case, sets of paths for each QoS (e.g., constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR)) are pre-calculated by computing the shortest path routes using a single optimization criteria for a single class of service. The routes provided are optimized without considering bandwidth (i.e., so long as a link has  greater than 0bandwidth it is used for the shortest path computation) and the method falls back to on-demand routing every time the search of pre-computed routes fails. In general, the pre-computed routes are stored in linear routing tables. Each routing table is maintained as a shortest path tree (SPT), and each SPT is constructed based on the optimization of a single traffic metric. In other words, each SPT maintains a shortest path tree to each reachable destination node in the same PNNI routing domain based on a single criterion, i.e., a traffic metric.
The use of such conventional routing tables, however, has several undesirable effects. For example, because multiple such tables are required to accommodate all of the various traffic metrics and service classes, a considerable amount of memory is required just to store the tables. Indeed, where all service classes exist in a network, a maximum number of these tables may have to be generated and stored. Further, because known routing algorithms can only optimize on a single constraint at a time, this suggests that any SPT made up of traditional routing tables will contain only those paths optimized for the designated traffic parameter. Yet, other parameters (which were not the subject of the route optimization computation) may also be determinative of whether a given route may be used by a connection request. This further increases the demand for sufficient memory to store the necessary routing tables.
What is desired, is a method for creating routing table structures for ATM or other networks that avoids the drawbacks of prior schemes.
The present invention provides a scheme for using distribution trees for point-to-multipoint connections within ATM or other computer networks.
In one embodiment, a dynamically created distribution tree for point-to-multipoint connections within a computer network may be created according to routing selections for at least one point-to-point connection of the point-to-multipoint connection. The routing selections may be made (e.g., optimized) according to traffic metrics advertised for service classes within the network. The traffic metrics may include administrative weight (AW), cell transfer delay (CTD) and cell delay variation (CDV). The service classes may include constant bit rate (CBR); real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR); available bit rate (ABR); and unspecified bit rate (UBR). The distribution tree may thus represent routes within the computer network optimized to share the routing selections made for the point-to-point connection.
In a further embodiment, dynamically generating a distribution table for a point-to-multipoint connection supported by an ATM network may be accomplished according to the number of connections shared by individual point-to-point connections that comprise the point-to-multipoint connection. The distribution table may be organized in a format having two dimensions with row indices thereof comprising PNNI node indices of succeeding nodes along a connection DTL. Individual entries in a first column of the distribution table may indicate PNNI node indices of proceeding nodes along the connection DTL. Individual entries in a second column of the distribution table may indicate the number of point-to-point connections for the point-to-multipoint connection that use a link connecting a pair of proceeding and succeeding nodes. A path may be selected from the distribution table in response to a request for a point-to-multipoint connection within the ATM network. Further, the distribution table may be updated in response to a call being added or dropped within the ATM network.
In yet another embodiment, a distribution table that includes a first column having network indices of nodes along a connection path of one or more point-to-point connections of a point-to-multipoint connection within a network; and a second column including values indicating the number of point-to-point connections for the point-to-multipoint connection that use a link connecting a pair of the nodes is provided. The network indices may be PNNI node indices and the network may be an ATM network. In some cases, the first column is indexable using network indices of succeeding nodes along the connection path and for each index of one of the succeeding nodes; an entry in the first column indicates a proceeding node thereof. Also, the connection path may be a path optimized according to the number of shared ones of the point-to-point connections of the point-to-multipoint connection.
In still a further embodiment, a distribution tree that includes a root node representing a source of a call within a network; one or more nodes representing intermediate hops or destinations for the call within the network; and one or more branches representing links that connect the root node to one or more of the nodes or pairs of the nodes is provided. In some cases, a table that is a two-dimensional representation of the distribution tree may be used.